package hebClustering.clusteringAlgorithms;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import hebClustering.Cluster;
import hebClustering.ClusterSet;
import hebClustering.vectorSpace.*;
import hebClustering.vectorSpace.distances.IDistance;


/**
 *	Implementation of the clustering algorithm K-means clustering.
 * 
 * 	@see <a href="http://en.wikipedia.org/wiki/K-means_clustering" target="_blank">K-means clustering</a>
 */
public class KMeansClustering implements IClusteringAlgorithm {
	protected int K,I;
	protected IDistance distance;
	
	public KMeansClustering(int K,int I,IDistance distance){
		this.K = K;
		this.distance = distance;
		this.I = I;
	}
	
	@Override
	public ClusterSet cluster(Collection<IVector> dataSet) {
		
		ClusterSet clusterSet = new ClusterSet();
		initializeMeans(dataSet,clusterSet);
		assignPointsToClusters(dataSet,clusterSet);
		
		boolean resultChanged = true;
		
		for(int i=0; i<I && resultChanged; i++){
			resultChanged = false;
			
			ClusterSet newClusterSet = new ClusterSet();
			
			for(Cluster cluster : clusterSet)
			{
				IVector newMean;
				
				/*If a cluster is found empty, get a new mean for it*/
				if( cluster.isEmpty() ){
					newMean = getMeanForEmptyCluster(clusterSet);
					resultChanged = true;
				}
				/*If not, find it's centroid and check if it is different from
				 * the old one*/
				else{
					newMean = cluster.findCentroid();
					
					if(!newMean.equals(cluster.getMean())){
						resultChanged = true;
					}
				}
				
				Cluster newCluster = new Cluster(newMean);
				newClusterSet.add(newCluster);
			}
			
			assignPointsToClusters(dataSet,newClusterSet);
			clusterSet = newClusterSet;
		}
		
		System.err.println(resultChanged? "need more iterations" : "good number of iterations");
		
		return clusterSet;
		
	}

	private IVector getMeanForEmptyCluster(ClusterSet clusterSet) {
		int maxNumber = 0;
        Cluster selected = null;
        for (Cluster cluster : clusterSet) {

            // get the number of points of the current cluster
            final int number = cluster.size();

            // select the cluster with the largest number of points
            if (number > maxNumber) {
                maxNumber = number;
                selected = cluster;
            }
        }
        
        // extract a random point from the cluster
        IVector mean = selected.getRandomVector();
        selected.remove(mean);
        return mean;
	}

	protected void assignPointsToClusters(Collection<IVector> dataSet,
			ClusterSet newClusterSet) {
		
		for(IVector v : dataSet) {
			Cluster cluster = getNearesetCluster(v,newClusterSet);
			cluster.add(v);
		}
		
	}

	protected Cluster getNearesetCluster(IVector v, ClusterSet clusterSet) {
		double minDistance = Double.MAX_VALUE;
		Cluster minCluster = null;
		
		for(Cluster cluster : clusterSet)
		{
			double dist = distance.calc(v, cluster.getMean());
			if(dist < minDistance){
				minDistance = dist;
				minCluster = cluster;
			}
		}
		
		return minCluster;
	}

	protected void initializeMeans(Collection<IVector> dataSet,ClusterSet clusterSet) {
		
		Collection<IVector> randomVectors = getRandomVectors(dataSet,K);
		
		for(IVector randomVec : randomVectors){
			Cluster cluster = new Cluster(randomVec);
			clusterSet.add(cluster);
		}
		
	}

	private Set<IVector> getRandomVectors(Collection<IVector> dataSet, int size) {
        
        List<IVector> randList = new ArrayList<IVector>(dataSet);
        Collections.shuffle(randList);
        
        Set<IVector> randSet = new HashSet<IVector>(randList.subList(0, size));
        
        return randSet;

	}
	
	public void setK(int K){
		this.K = K;
	}
	
	
}
